package generateParenthesis22;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    public static void main(String[] args) {
        GenerateParenthesis generateParenthesis = new GenerateParenthesis();
        List<String> strings = generateParenthesis.generateParenthesis(3);
        System.out.println(strings);
    }

    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        dfs(n, n, "");
        return res;
    }

    /**深度优先遍历
     * @param left 左括号还有几个能用
     * @param right 右括号还有几个能用
     * @param curStr
     */
    private void dfs(int left, int right, String curStr) {
        if(left ==0&&right==0){
            res.add(curStr);
            return;
        }
        //此处注意左括号剩余的一定小于右括号剩余，比如n=2 就不能出现 ()) 这种的 左括号剩余1个右括号剩余0.所以一旦左边大于右边剩余则跳出递归
        if(left>right){
            return;
        }

        //https://gitee.com/z_lamber/image-bed/raw/master/20210924161950.png
        //说明还有左括号可以继续拼接
        if(left>0){
            dfs(left-1,right,curStr+"(");
        }
        if(right>0){
            dfs(left,right-1,curStr+")");
        }
    }

}
